/**
 * 双指针，通过左右数组判断当前index装的雨水，每一列
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let leftMax = new Array(height.length).fill(0),
        rightMax = new Array(height.length).fill(0),
        sum = 0,
        len = height.length;

    leftMax[0] = height[0]
    for (let i = 1; i < len; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i])
    }
    rightMax[len - 1] = height[len - 1]
    for (let i = len - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i])
    }

    for (let i = 1; i < len - 1; i++) {
        sum += Math.min(leftMax[i], rightMax[i]) - height[i]
    }

    return sum
};

/**
 * 单调栈，通过行相加
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let stack = [],
        sum = 0,
        len = height.length;

    for (let i = 0; i < height.length; i++) {
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            let mid = stack.pop()
            if (stack.length > 0) {
                let left = stack[stack.length - 1],
                    width = i - left - 1,
                    hei = Math.min(height[i], height[left]) - height[mid];
                sum += width * hei
            }
        }
        stack.push(i)
    }
    return sum
};